﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<stdbool.h>
#include<stdio.h>
//1;缺失的第一个正数
int firstMissingPositive(int* nums, int numsSize) {
	///没有出现的第一个正数的范围1——>size + 1
	//首先遍历是否存在1，如果没有1，缺失的第一个正数就是1
	int i = 0;
	for (i = 0; i < numsSize; i++)
	{
		if (nums[i] == 1)
			break;
	}
	if (i == numsSize)
		return 1;
	//再次遍历，将>numssize 和负数全部都变为1
	for (i = 0; i < numsSize; i++)
	{
		if (nums[i] <= 0 || nums[i] > numsSize)
			nums[i] = 1;
	}
	//再次遍历，将值对应位置的元素标记为负数
	for (i = 0; i < numsSize; i++)
	{
		nums[abs(nums[i]) - 1] = -abs(nums[abs(nums[i]) - 1]);
	}
	//最后遍历，第一个是正数的位置（下标） + 1就是缺失的正数
	for (i = 0; i < numsSize; i++)
	{
		if (nums[i] > 0)
			return i + 1;
	}
	//如果都是负数，就返回numssize + 1
	return numsSize + 1;
}

//2：单值二叉树

struct TreeNode
{
	int val;
	struct TreeNode* left;
	struct TreeNode* right;
};

bool isUnivalTree(struct TreeNode* root) {
	//思路：a == b, a == c, 那么a == c == b,先判断根和左子树的根是否相等，如果相等或左子树不存在，就继续，否则停止，如果左子树等值，再用相同的思路比较右子树，只有左右子树都是等值，整棵树才等值
	if (root == NULL)
		return true;
	if (root->left && root->val != root->left->val)
		return false;
	if (root->right && root->val != root->right->val)
		return false;
	return isUnivalTree(root->left) && isUnivalTree(root->right);
}


//3:二叉树的最大深度
int Max(int x, int y)
{
	return x > y ? x : y;
}

int maxDepth(struct TreeNode* root) {
	/*如果我们知道了左子树和右子树的最大深度 l 和 r，那么该二叉树的最大深度即为

	max⁡(l,r)+1
	而左子树和右子树的最大深度又可以以同样的方式进行计算。
	*/
	if (root == NULL)
		return 0;
	return 1 + Max(maxDepth(root->left), maxDepth(root->right));
}